// 面试题 3: 数组中重复的数字
// 题目：在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如，如果输入长度为 7 的数组 {2, 3, 1, 0, 2, 5, 3} ，那么对应的输出是重复的数字 2 或者 3 。
// 考点：
//  - 数组中的数字都在 0 ~ n-1 之间。如果这个数组中没有重复的数字，那么当数组排序之后数字 i 将出现在下标为 i 的位置。由于数组中有重复的数字，有些位置可能存在多个数字，同时有些位置可能没有数字。
//  - 算法的空间复杂度是 O(1)
//  - 算法的时间复杂的是 O(N)

#include <cassert>

bool duplicate(int *numbers, int length, int *duplication)
{
    if (numbers == nullptr || length <= 0)
        return false;

    for (int i = 0; i < length; i++)
    {
        if (numbers[i] < 0 || numbers[i] >= length)
            return false;
    }

    for (int i = 0; i < length; i++)
    {
        for (;;)
        {
            int val = numbers[i];
            if (i == val)
                break;

            if (numbers[val] == val)
            {
                *duplication = val;
                return true;
            }
            else
            {
                int temp = numbers[val];
                numbers[val] = val;
                numbers[i] = temp;
            }
        }
    }

    return false;
}

// 重复的数字是数组中最小的数字
void test1()
{
    int numbers[] = {1, 2, 3, 4, 1};
    int val;
    bool ret = duplicate(numbers, 5, &val);
    assert(ret == true);
    assert(val == 1);
}

// 重复的数字是数组中最大的数字
void test2()
{
    int numbers[] = {4, 0, 1, 4, 2};
    int val;
    bool ret = duplicate(numbers, 5, &val);
    assert(ret == true);
    assert(val == 4);
}

// 数组中存在多个重复的数字
void test3()
{
    int numbers[] = {4, 0, 1, 4, 1};
    int val;
    bool ret = duplicate(numbers, 5, &val);
    assert(ret == true);
    assert(val == 1);
}

// 没有重复的数字
void test4()
{
    int numbers[] = {3, 0, 1, 2, 4};
    int val;
    bool ret = duplicate(numbers, 5, &val);
    assert(ret == false);
}

// 无效的输入
void test5()
{
    int numbers[] = {3, 5, 1, 2, 4};
    int val;
    bool ret = duplicate(numbers, 5, &val);
    assert(ret == false);
}

// 无效的输入
void test6()
{
    int *numbers = nullptr;
    int val;
    bool ret = duplicate(numbers, 5, &val);
    assert(ret == false);
}

int main()
{
    test1(); 
    test2();
    test3();
    test4();
    test5();
    test6();
}

